Curso Académico:
2023/24
453 - Graduado en Matemáticas
27005 - Grafos y combinatoria
Información del Plan Docente
Año académico:
2023/24
Asignatura:
27005 - Grafos y combinatoria
Centro académico:
100 - Facultad de Ciencias
Titulación:
453 - Graduado en Matemáticas
Créditos:
6.0
Curso:
1
Periodo de impartición:
Segundo semestre
Clase de asignatura:
Obligatoria
Materia:
---
1. Información básica de la asignatura
En la resolución de diferentes problemas científicos, aparecen de forma natural cuestiones de tipo combinatorio o de teoría de grafos, que es importante saber reconocer y saber resolver. Por ello, el objetivo fundamental de esta asignatura es presentar las técnicas básicas del análisis combinatorio, así como los métodos y algoritmos de resolución de problemas básicos sobre grafos.
Los planteamientos y objetivos de la asignatura están alineados con los Objetivos de Desarrollo Sostenible (ODS) de la Agenda 2030 de Naciones Unidas; en concreto, las actividades de aprendizaje previstas en esta asignatura contribuirán en alguna medida al logro de los objetivos 4 (educación de calidad), 5 (igualdad de género), 8 (trabajo decente y crecimiento económico) y 10 (reducción de las desigualdades).
2. Resultados de aprendizaje
- Resolver problemas elementales de ordenación y enumeración.
- Conocer y manejar el concepto de función generatriz y el de fórmula de recurrencia.
- Utilizar las funciones generatrices para obtener fórmulas para problemas de enumeración.
- Conocer el lenguaje y las aplicaciones más elementales de la teoría de grafos.
- Aplicar los algoritmos básicos de teoría de grafos para resolver problemas.
3. Programa de la asignatura
TEMA I
- Combinatoria elemental. Permutaciones y combinaciones.
- Coeficientes binomiales.
- Recurrencias. Aplicaciones.
- El principio de inclusión-exclusión. Aplicaciones.
TEMA II
- Funciones generatrices.
- Funciones generatrices racionales.
TEMA III
- Definición y notaciones para grafos.
- Problema de recorrido de un grafo. Algoritmos BFS y DFS.
- Aplicaciones. Cálculo de componentes y bases.
- Número de árboles y caminos de un grafo.
TEMA IV
- Grafos con costos. Algoritmos para calcular el árbol mínimo.
- Caminos más cortos: Algoritmo de Dijkstra.
- Técnicas PERT-CPM de planificación de proyectos.
TEMA V
- Flujo en redes. Conceptos básicos.
- Algoritmo de Ford- Fulkerson para cálculo de máximo flujo.
- Teoremas de conectividad de Menger.
- Matching en grafos bipartitos. Teorema de Hall.
- Algunos problemas NP-duros sobre grafos.
4. Actividades académicas
Clases magistrales: 30 horas.
Resolución de problemas y casos: 30 horas.
Estudio: 84 horas.
Pruebas de evaluación: 6 horas.
5. Sistema de evaluación
Al terminar la primera parte de la asignatura (temas de combinatoria), se realizará una prueba parcial, donde se examinará al alumno sobre esos contenidos de combinatoria y se le calificará con una nota, P1, entre 0 y 10.
En la fecha oficial de una convocatoria se realizará un examen con dos partes diferenciadas, una con preguntas de combinatoria, la otra con cuestiones de teoría de grafos. Las calificaciones obtenidas en cada una de esas partes (E1 y E2) serán también sobre 10 puntos.
La calificación, C, de la asignatura, obtenida en esa convocatoria oficial será:
- Si P1 es menor que 4, C = 0.5*(E1+E2).
- Si P1 es mayor o igual que 4, C = 0.5*(Max(P1,E1)+E2).
Habrán superado la asignatura en esa convocatoria quienes hayan obtenido una calificación C mayor o igual a 5.